package src.skill_problem;

import java.util.Arrays;
import java.util.HashMap;

public class no169 {  //找数组中的众数

    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }

    public int majorityElement2(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }
        int maxCount = 0;
        for (int i : map.keySet()) {
            int count = map.get(i);
            maxCount = Math.max(maxCount, count);
        }
        for (int i : map.keySet()) {
            if (map.get(i) == maxCount) {
                return i;
            }
        }
        return -1;
    }

    /**
     *     最优解法：摩尔投票法，抵消原则。由于众数超过一半，所以不同的两个数相消，最终剩下的一定是众数
     */
    public int majorityElement3(int[] nums) {
        int count = 1;  //count只会为 0、1 两种情况
        int res = nums[0];  //一开始先假设nums[0]就是众数
        for (int i = 1; i < nums.length; i++) {
            //一上来先检查当前count是否为0，为0则说明前面两个数不同 抵消了，因此再假设当前元素为众数
            if (count == 0) {
                res = nums[i];
            }
            if (nums[i] == res) {
                count++;
            } else {
                count--;
            }
        }
        return res;

    }
}
